package leetcode.code542.Matrix01;


import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * 队列，队列里放入没看过的点。
 * ps ： 放看过的点或许更快。
 *
 * @author Max
 * @date 2021年8月20日
 * @description
 */
public class Solution54202 extends Matrix01 {

	/**
	 * m == mat.length n == mat[i].length 1 <= m, n <= 104 1 <= m * n <= 104
	 * mat[i][j] is either 0 or 1. mat 中至少有一个 0 
	 */
	@Override
	public int[][] updateMatrix(int[][] mat) {
		int h = mat.length;
		int w = mat[0].length;
		int[][] res = new int[h][w];
		Queue<int[]> q = new LinkedList<>();
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (mat[i][j] == 0) {
					res[i][j] = 0;
				} else {
					res[i][j] = -1;
					q.add(new int[] { i, j });
				}
			}
		}
		int start = 0;
		int len = q.size();
		while (!q.isEmpty()) {
			int[] pos = q.poll();
			if (findMinAround(res, pos[0], pos[1], start)) {
				res[pos[0]][pos[1]] = start + 1;
			} else {
				q.add(pos);
			}
			len--;
			if (len == 0) {
				len = q.size();
				start++;
			}
		}
		return res;
	}

	public boolean findMinAround(int[][] mat, int x, int y, int target) {
		boolean a, b, c, d;
		if (y >= 0 && y < mat[0].length) {
			a = x + 1 < mat.length ? (mat[x + 1][y] == target ? true : false) : false;
			if (a)
				return a;
			b = x - 1 >= 0 ? (mat[x - 1][y] == target ? true : false) : false;
			if (b)
				return b;
		}
		if (x >= 0 && x < mat.length) {
			c = y - 1 >= 0 ? (mat[x][y - 1] == target ? true : false) : false;
			if (c)
				return c;
			d = y + 1 < mat[0].length ? (mat[x][y + 1] == target ? true : false) : false;
			if (d)
				return d;
		}
		return false;
	}

	/**
	 * 某一个点的最小值
	 *
	 * @param mat
	 * @param x
	 * @param y
	 * @return
	 */
	public void plusOne(int[][] mat, int x, int y, int expect) {
		if (x >= 0 && y >= 0 && x < mat.length && y < mat[0].length && mat[x][y] != 0) {
			mat[x][y] = expect;
		}
	}

	public int min(int[][] mat, int x, int y) {
		if (x >= 0 && y >= 0 && x < mat.length && y < mat[0].length) {
			return Math.min(min(mat, x, y + 1),
					Math.min(min(mat, x, y - 1), Math.min(min(mat, x - 1, y), min(mat, x + 1, y)))) + 1;
		}
		return Integer.MAX_VALUE;
	}

	public void plus(int[][] mat, int x, int y, int expect) {
		if (x >= 0 && y >= 0 && x < mat.length && y < mat[0].length && (mat[x][y] != 0 || mat[x][y] != 1)) {
			if (mat[x][y] >= expect) {
				mat[x][y] = expect;
				plus(mat, x + 1, y, expect + 1);
				plus(mat, x - 1, y, expect + 1);
				plus(mat, x, y + 1, expect + 1);
				plus(mat, x, y - 1, expect + 1);
			}
		}
	}

	public static void main(String[] args) {
		Solution54202 so = new Solution54202();
//		so.debug1();
//		so.debug2();
//		so.debug3();
		so.debug4();
	}

}
